#include <vector>
#include <stack>

using namespace std;

int maxArea(vector<int> &height) {
    int n = height.size();
    stack<int> pl;
    int i = 0;
    int max_area = 0;
    while (i <= n) {
        if (i == n || (!pl.empty() && height[pl.top()] > height[i])) {
            int t = pl.top();
            pl.pop();
            if (!pl.empty()) {
                int width = pl.empty() ? i : i - pl.top() - 1;
                if (max_area < width * height[t]) {
                    max_area = width * height[t];
                }
            }
            else {
                break;
            }
        }
        else {
            pl.push(i);
            i++;
        }
    }
    
    return max_area;
}

int maximalRectangle(vector<vector<char> > &matrix) {
    int row_num = matrix.size();
    int col_num = matrix[0].size();
    
    vector<int> col(col_num, 0);
    vector<vector<int> > am(2, col);
    
    int i, j;
    for (j = 0; j < col_num; j++) {
        if (matrix[0][j]) {
            am[0][j]++;
        }
    }
    int max_area = maxArea(am[0]);
    
    for (i = 1; i < row_num; i++) {
        for (j = 0; j < col_num; j++) {
            if (matrix[i][j]) {
                am[i&1][j] = am[(i - 1)&1][j] + 1;
            }
            else {
                am[i&1][j] = 0;
            }
        }
        int area = maxArea(am[i&1]);
        if (max_area < area) {
            max_area = area;
        }
    }

    return max_area;
}
